import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class Leetcode206 {
    public static void main(String[] args) {
        ListNode res = new ListNode();
        Leetcode19.createNode(res, new ArrayList<>(List.of(1)));
        res = reverseList(res);

        System.out.println(res);
    }

    public static ListNode reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();
        ListNode next = head;
        while (next != null) {
            stack.add(next);
            next = next.next;
        }

        if (stack.isEmpty()) {
            return null;
        }

        if (stack.size() == 1) {
            return head;
        }

        ListNode res = stack.pop();
        res.next = new ListNode();
        ListNode resNext = res.next;
        while (!stack.isEmpty()) {
            resNext.val = stack.pop().val;

            if (resNext.next == null && stack.size() != 0) {
                resNext.next = new ListNode();
            }

            resNext = resNext.next;
        }

        return res;
    }

    public static ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode newHead = reverseList1(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}
